﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace IJK
{
    public partial class frmIJK : Form
    {
        public frmIJK()
        {
            InitializeComponent();
        }

        const int MAXTS = 1000;
        const int MAXn = 12;
        const int MAXslCanh = (MAXn + 1) * MAXn / 2;
        //Luu vi tri chuot khi click chuot trai
        Point cPoint = new Point(0);
        //ban kinh mac dinh cho duong tron
        int rDefault;
        int i;
        int j;
        int j1;
        int sodinh;
        int m;
        Boolean bl;
        Graphics gra;
        int[,] a;
        int[] x;
        int[] y;
        Label[] dslb;
        MaskedTextBox[] dstx;
        Label[] dsVe; int countdsVe;
        bool firstDraw;

        private void btnThoat_Click(object sender, EventArgs e)
        {
            this.Close();
        }

        private void btnReset_Click(object sender, EventArgs e)
        {
            cbbBatDau.Enabled = false;
            cbbKetThuc.Enabled = false;
            btnXemDuongDi.Enabled = false;
            bl = false;
            btnKetThuc.Enabled = false;
            btnVeDoThi.Enabled = false;
            gra = this.CreateGraphics();
            
            //dinh nghia panel
            Panel pn1 = new Panel();
             rDefault = 30;
             i = 0;
             j = 0;
             j1 = 0;
             sodinh = 0;

             a = new int[MAXn, MAXn];
             x = new int[MAXn];
             y = new int[MAXn];

             grbKQ.Visible = false;
             lbDiemVe.Visible = false;
             cbbBatDau.Visible = false;
             cbbBatDau.Items.Clear();
             cbbBatDau.Text = "";
             //cbbKetThuc.SelectedIndex = -1;


            lbKetThuc.Visible = false;
             cbbKetThuc.Visible = false;
             cbbKetThuc.Items.Clear();
             cbbKetThuc.Text = "";
             //cbbKetThuc.SelectedIndex = -1;

             label1.Text = "";
             label2.Text = "";

             if (dslb != null)
             {
                 int lcount = 1;
                 while (dslb[lcount] != null)
                 {
                     dslb[lcount].Visible = false;
                     dstx[lcount].Visible = false;
                     lcount++;
                 }
             }

             dslb = new Label[MAXslCanh];
             dstx = new MaskedTextBox[MAXslCanh];
            
             m = 0;

             if (dsVe != null)
             {
                 for (int lc = 0; lc < MAXslCanh + MAXn; lc++)
                 {
                     if (dsVe[lc] != null)
                         dsVe[lc].Visible = false;
                 }
             }

             dsVe = new Label[MAXslCanh + MAXn]; countdsVe = 0;
             this.Refresh();
             firstDraw = true;
        }  

        private void frmIJK_Load(object sender, EventArgs e)
        {
            btnReset.PerformClick();
        }


        private void frmIJK_MouseDown(object sender, MouseEventArgs e)
        {
            if (!bl)
            {
                if (i < MAXn)
                {
                    cPoint = e.Location;
                    int ex = cPoint.X;
                    int ey = cPoint.Y;
                    if (CheckDrawCircle(e))
                    {
                        btnKetThuc.Enabled = true;

                        rDefault = 30;
                        DrawCircle();
                        x[i] = cPoint.X;
                        y[i] = cPoint.Y;
                        i++;
                    }
                }
                else
                {
                    MessageBox.Show("Bạn chỉ có thể nhập 12 điểm");
                    btnKetThuc.PerformClick();
                }
            }
        }

        private bool CheckDrawCircle(MouseEventArgs e)
        {
            bool a = (bl == false && e.Location.X >= 25 && e.Location.Y >= 120 && e.Location.X < 1200 && e.Location.Y <= 450);
            bool b = true;
            for (int lk = 0; lk < i; lk++)
            {
                b = b && !((e.X < (x[lk] + rDefault * 2) && e.X > (x[lk] - rDefault * 2)) && (e.Y < (y[lk] + rDefault * 2) && e.Y > (y[lk] - rDefault * 2)));
            }
            return a && b;
       
        }
        private void DrawCircle()
        {
            Graphics g = this.CreateGraphics();
            Pen p = new Pen(new SolidBrush(Color.Black), 2);
            string a = Convert.ToString(i);
            int dx = rDefault / 2;
            //Ve hinh tron
            //g.DrawEllipse(p, cPoint.X-dx, cPoint.Y-dx, rDefault, rDefault);
            //g.Dispose();
            Label lb = new Label();
            lb.Location = new Point(cPoint.X-7, cPoint.Y-5);
            lb.Text = a;
            lb.Size = new Size(30, 20);
            lb.BorderStyle = BorderStyle.Fixed3D;
            lb.TextAlign = ContentAlignment.MiddleCenter;
            this.Controls.Add(lb);
            dsVe[countdsVe] = lb; countdsVe++;
          
        }
        //protected override void OnPaint(PaintEventArgs paintEvnt)
        //{
        //    DrawCircle();
        //}
        private int Dijkstra(int n, int s, int e)
        {
            #region thuat toan dijkstra
            int[] Chua = new int[MAXn];
            int[] d = new int[MAXn];
            int[] T = new int[MAXn];
                int last = 0;
                int min = 0;
                int dem = 0;
            //khoi tao
                for (int i = 0; i < n; i++)
                {
                    d[i] = MAXTS;    //tu dinh s den cac dinh con lai la vo cuc
                    Chua[i] = 0;    //chua co dinh nao duoc chon vao cay T
                    T[i] = s;   //s la dinh truoc khi den tat ca dinh i con lai
                }
                for (int j = 0; j < n; j++)
                {
                    if (a[s,j]!=0)  //neu co canh noi giua s va j
                        d[j] = a[s,j];  //luu lai khoang cach s-->j vao mang d
                }
                d[s] = 0; //khoang cach s-s la 0 (d la mag luu lai khoang cach tinh tu s)
                Chua[s] = 1;    //s la dinh dau tien dua vao cay T
                dem = n - 1;    //chuan bi lap n-1 lan , chon n-1 dinh con lai vao cay T (s da chon rui)
                while (dem > 0) // lan luot chon n-1 dinh dua vao cay T
                {
                    min = 2 * MAXTS;     //nhan doi de so trung vo cuc
                    for(int i=0;i<n;i++)    //tim dinh I 
                        if ((Chua[i] == 0) && (d[i] <= min))    //last ngoai cay T, d[last] nho nhat
                        {
                            min = d[i];
                            last = i;
                        }
                    if (min == 2 * MAXTS)
                    {
                        //MessageBox.Show("Đồ thị không liên thông");
                        label1.Text = "Đồ thị không liên thông";
                        return 0;
                    }
                    Chua[last] = 1;
                    //chon duoc last dua vao cay T
                    for(int j=0;j<n;j++)    //cap nhat lai gia tri
                        if ((Chua[j] == 0) && (d[last] + a[last, j] < d[j]))
                        {
                            d[j] = d[last] + a[last, j];
                            T[j] = last;
                        }
                    dem--;
                }
                #endregion

                #region xuat

                // In kq: dinh goc xp --> tat ca dinh con lai
                if (e != s)    //neu la dinh goc => khong in ra man hinh
                    if (d[e] == MAXTS)  //ko co duong di tu s - i
                        label1.Text = "không có đường đi";
                    else 
                    {
                        label1.Text = "Đường đi có độ dài là: " + d[e];
                        //string strout = Convert.ToString(e);
                        int[] intout = new int[MAXn];
                        intout[0] = e;
                        int cout = 1;
                        #region
                        //int[] mang = new int[20];
                        //dem = 0;
                        //int tam = T[i];
                        //while (tam != s)
                        //{
                        //    mang[dem] = tam;
                        //    tam = T[tam];
                        //    dem++;
                        //}
                        //if (dem > 0)
                        //{
                        //    veduong1(x[s], y[s], x[mang[dem - 1]], y[mang[dem - 1]], Convert.ToString(a[s, mang[dem - 1]]));
                        //    label2.Text += Convert.ToString(mang[dem - 1]) + "->";
                        //    for (int j = dem; j > 0; j--)
                        //        if (j - 2 >= 0)
                        //        {
                        //            veduong1(x[mang[j - 1]], y[mang[j - 1]], x[mang[j - 2]], y[mang[j - 2]], Convert.ToString(a[mang[j - 1], mang[j - 2]]));
                        //            label2.Text += Convert.ToString(mang[j - 2]) + "->";
                        //        }
                        //    veduong1(x[mang[0]], y[mang[0]], x[e], y[e], Convert.ToString(a[s, e]));
                        //}
                        //else if (dem == 0 && a[s, e] != 0)
                        //{
                        //    veduong1(x[s], y[s], x[e], y[e], Convert.ToString(a[s, e]));
                        //}
                        //    label2.Text += Convert.ToString(e);
                        #endregion
                        string l2Text = "Đi qua các đỉnh: ";
                        int lk = e;
                        veduong1(x[lk], y[lk], x[T[lk]], y[T[lk]], a[lk, T[lk]].ToString());
                        lk = T[e];
                        while (lk != s)
                        {
                            //strout += "<-" + Convert.ToString(lk);
                            intout[cout] = lk; cout++;
                            veduong1(x[lk], y[lk], x[T[lk]], y[T[lk]], a[lk, T[lk]].ToString());
                            lk = T[lk];
                        } 
                        //while (lk != s);
                        //strout += "<-" + Convert.ToString(s);
                        intout[cout] = s;
                        #region dao ngc chuoi
                        //string s = "abcd";
                        //tách chuỗi thành từng kí tự đưa lưu vào mảng 1 chiều
                        //char[] c = strout.ToCharArray();
                        //đảo ngược mảng
                        //Array.Reverse(intout);
                        for (int tk = cout; tk >= 0; tk--)
                        {
                            l2Text = l2Text + intout[tk] + "->";
                        }
                        //l2Text = l2Text + intout[cout];
                        #endregion
                        label2.Text = l2Text;

                    }
                else label1.Text = "Đỉnh đầu trùng đỉnh cuối";
                return 1;
            #endregion
        }

        private void veduong1(int x1, int y1, int x2, int y2, string ch)
        {
            Pen p = new Pen(Color.Red);
            gra.DrawLine(p, x1, y1, x2, y2);
            Label lb = new Label();
            lb.Location = new Point((x1 + x2) / 2, (y1 + y2) / 2);
            lb.Text = ch;
            int lk = 7 + ch.Length * 6;
            lb.Size = new Size(lk, 13);
            this.Controls.Add(lb);
            dsVe[countdsVe] = lb; countdsVe++;
        }
        private void btnKetThuc_Click(object sender, EventArgs e)
        {
            #region Nut ket thuc nhap
            bl = true;
            string ch1 = "Trọng số ";
            sodinh = i;
            for(int k=0;k<sodinh;k++)
                for (int l = k; l < sodinh; l++)
                {
                    if (k != l)
                    {
                        m++;
                        string k1 = Convert.ToString(k);
                        string l1 = Convert.ToString(l);
                        string k2 = " (";
                        string k3 = " ,";
                        string k4 = " )";
                        string m1 = Convert.ToString(m);
                        string ch2 = string.Concat(ch1, k2, k1, k3, l1, k4);
                        //create_label(600, 80, ch2);
                        create_label(20, 487, ch2);
                        //if (m <= 20)
                        //    j += 20;
                        //else
                        //    j1 += 20;
                        if (m <= 12)
                            j += 20;
                        else
                            j1 += 20;
                    }
                }
            j = j1 = m = 0;
            for (int k = 0; k < sodinh; k++)
            {
                for (int l = k; l < sodinh; l++)
                {
                    if (k != l)
                    {
                        m++;
                        //Tiep tuc
                        string k1 = Convert.ToString(k);
                        string l1 = Convert.ToString(l);
                        string k2 = " (";
                        string k3 = " ,";
                        string k4 = " )";
                        string k5 = "txt";
                        string m1 = Convert.ToString(m);
                        //m1 = "VC";
                        string ch2 = string.Concat(ch1, k2, k1, k3, l1, k4);
                        create_textbox(120, 487, string.Concat(k5, m1));
                        if (m <= 12)
                            j += 20;
                        else
                            j1 += 20;
                    }
                }
            }
            btnVeDoThi.Enabled = true;
            btnKetThuc.Enabled = false;
            #endregion
        }
        private void create_label(int x, int y, string ch)
        {
            
            #region create label
            if (m <= 12)
            {
                Label lb = new Label();
                lb.Location = new Point(x, y + j);
                lb.Text = ch;
                lb.Size = new Size(100, 17);
                this.Controls.Add(lb);
                dslb[m] = lb;
            }
            else if (m > 12)
            {
                j = 0;
                x += 200 * ((m-1) / 12);
                if ((m - 1) % 12 == 0)
                    j1 = 0;
                Label lb = new Label();
                lb.Location = new Point(x, y + j1);
                lb.Text = ch;
                lb.Size = new Size(100, 17);
                this.Controls.Add(lb);
                dslb[m] = lb;
            }
            #endregion
        }
        private void create_textbox(int x, int y, string ch)
        {
            
            #region tao text box
            if (m <= 12)
            {
                MaskedTextBox tb = new MaskedTextBox("000");
                tb.Location = new Point(x, y + j);
                tb.Name = ch;
                tb.Size = new Size(50, 30);
                //tb.Text = "___";
                this.Controls.Add(tb);
                dstx[m] = tb;
            }
            else if (m > 12)
            {
                j = 0;
                x += 200 * ((m - 1) / 12);
                if ((m - 1) % 12 == 0)
                    j1 = 0;
                MaskedTextBox tb = new MaskedTextBox("000");
                tb.Location = new Point(x, y + j1);
                tb.Name = ch;
                tb.Size = new Size(50, 30);
                //tb.Text = "";
                this.Controls.Add(tb);
                dstx[m] = tb;
            }
            #endregion
        }
        private void veduong(int x1, int y1, int x2, int y2, string ch)
        {
            #region ve duong
            Pen p = new Pen(Color.Black);
            gra.DrawLine(p, x1, y1, x2, y2);
            Label lb = new Label();
            lb.Location = new Point((x1 + x2) / 2, (y1 + y2) / 2);
            lb.Text = ch;
            int lk = 7 + ch.Length * 6;
            lb.Size = new Size(lk, 13);
            this.Controls.Add(lb);
            dsVe[countdsVe] = lb; countdsVe++;
            #endregion
        }

        private void XoaNhapTrongSo()
        {
            for (int lk = 1; lk <= m; lk++)
            {
                dslb[lk].Visible = false;
                dstx[lk].Visible = false;
            }
        }

        private void VeDoThiDen()
        {
            if (countdsVe >= (MAXslCanh - (sodinh +1)*sodinh/2))
            {
                for (int tk = sodinh + 1; tk <= countdsVe; tk++)
                {
                    if (dsVe[tk] != null)
                        dsVe[tk].Visible = false;
                    
                }
                countdsVe = sodinh + 1;
            }
            for (int lx = 0; lx < sodinh -1; lx++)
            {
                for (int ly = lx +1; ly < sodinh; ly++)
                {
                    if (a[lx, ly] != MAXTS && a[lx, ly] != 0)
                        veduong(x[lx], y[lx], x[ly], y[ly], a[lx, ly].ToString());
                }

            }
        }

        private void btnVeDoThi_Click(object sender, EventArgs e)
        {
            #region nut ve do thi
            grbKQ.Visible = true;
            lbDiemVe.Visible = true;
            cbbBatDau.Visible = true;
            lbKetThuc.Visible = true;
            cbbKetThuc.Visible = true;
            if (firstDraw)
            {
                cbbBatDau.Enabled = true;
                for (int k1 = 0; k1 < sodinh; k1++)
                {
                    cbbBatDau.Items.Add(Convert.ToString(k1));
                    cbbKetThuc.Items.Add(Convert.ToString(k1));
                }
                firstDraw = false;
            }
            #region
            //int n = 0;
            //int socontrol = this.Controls.Count;
            //for (int k = 0; k < sodinh; k++)
            //{
            //    for (int l = k; l < sodinh; l++)
            //    {
            //        if (k != l)
            //        {
            //            try
            //            {
            //                a[k, l] = Convert.ToInt32(this.Controls[socontrol - (m - n)].Text);
            //            }
            //            catch (Exception ex)
            //            {
            //                MessageBox.Show(ex.Message);
            //                MessageBox.Show(this.Controls[socontrol].Text + m);
            //            }
            //            a[l, k] = a[k, l];
            //            if (a[k, l] != 0)
            //            {
            //                veduong(x[k], y[k], x[l], y[l], Convert.ToString(a[k, l]));
            //            }
            //            n++;
            //        }
            //        else a[k, l] = 0;
            //    }
            //}
            #endregion
            a = new int[sodinh, sodinh];
            int lcount = 1;
            for (int lx = 0; lx < sodinh - 1; lx++)
            {
                for (int ly = lx + 1; ly < sodinh; ly++)
                {
                    string ltx = dstx[lcount].Text;
                    ltx = ltx.Replace("_", "");
                    if (ltx != "")
                    {
                        try
                        {
                            int lin = int.Parse(ltx);
                            a[lx, ly] = lin;
                            a[ly, lx] = lin;
                            
                        }
                        catch (Exception)
                        {

                        }
                    }
                    else 
                    {
                        a[lx, ly] = MAXTS;
                        a[ly, lx] = MAXTS;
                    }
                    lcount++;
                }
            }


            XoaNhapTrongSo();
            //btnVeDoThi.Enabled = false;
            VeDoThiDen();
            #endregion
        }

        private void cbbBatDau_SelectedIndexChanged(object sender, EventArgs e)
        {
            cbbKetThuc.Enabled = true;
        }

        private void cbbKetThuc_SelectedIndexChanged(object sender, EventArgs e)
        {
            btnXemDuongDi.Enabled = true;
        }

        private void btnXemDuongDi_Click(object sender, EventArgs e)
        {
            //btnVeDoThi.PerformClick();
            VeDoThiDen();
            #region Nut xem duong di
            string st;
            string en;
            int ist;
            int ien;
            st = cbbBatDau.Text;
            en = cbbKetThuc.Text;
            label1.Text = "";
            label2.Text = "";
            
            try
            {
                if (cbbBatDau.Text != "" || cbbKetThuc.Text != "")
                {
                    ist = Convert.ToInt32(st);
                    ien = Convert.ToInt32(en);
                    if (Dijkstra(sodinh, ist, ien) == 0)
                        //MessageBox.Show("Không có đường đi ");
                        label1.Text = "Không có đường đi ";
                }
                else
                    //MessageBox.Show("Chọn đỉnh xuất phát và đỉnh đích !");
                    label1.Text = "Chọn đỉnh xuất phát và đỉnh đích !";
            }
            catch (Exception ex)
            {
                //MessageBox.Show(ex.Message);
                label1.Text = ex.Message;
            }
            #endregion
        }
    }
}
